/*file: searchPrime.gp*/

/* calculate b^e \mod m */
modexp(b, e, m) = {
	local(r, bin, i);
	r = 1;
	bin = binary (e);
	for ( i = 1, length(bin),
		r = (r*r) % m;
		if( bin[i] == 1,
			r = (r*b) % m;
		);
	);
	return (r);
}

calcNextPollardElement(y, k, l, g, h, p)=
{
	local(r);
	/*global(g, h, p);*/
	r = y % 3;
	if(r == 0,
		k = (k+1) % (p-1);
	);
	if (r == 1,
		l = (l+1) % (p-1);
	);
	if (r == 2,
	 	k = (2*k) % (p-1);
		l = (2*l) % (p-1);
	);
	y = (modexp(g,k,p) * modexp(h,l,p) ) % p;

	[y, k,l];
}

/*
p__ = nextprime(2^160);
h__ = 15;
g__ = lift(znprimroot(p__));
k__ = random(p__ - 1);
print (k__);

l__ = random(p__ - 1);
print (l__)

y_0__ = (modexp(g__, k__, p__) * modexp(h__, l__, p__) ) % p__;

y = calcNextPollardElement(y_0__, k__, l__, g__, h__, p__);
print (y);
*/


testCalcNextPollardElement(r)=
{
	local(p__, h__, g__, k__, l__);
	local(y);
	local(i = 0);
	local(t = 0);
	local(pq);
	read("./searchPrime.gp");
	pq = searchSafePrime(primeSize);
	p__ =  pq[1]; /*nextprime(2^160);*/
	h__ = 13;

	g__ = lift(znprimroot(p__));
	k__ = random(p__ - 1);

	l__ = random(p__ - 1);

	y_0__ = (modexp(g__, k__, p__) * modexp(h__, l__, p__) ) % p__;

	y = calcNextPollardElement(y_0__, k__, l__, g__, h__, p__);

	t = gettime();
	print (t);
	while (i < r,
		i++;
		y = calcNextPollardElement( y[1], y[2], y[3], g__, h__, p__);
		print (g__);
		print (h__);
		print (p);
		/*print (y);*/
	);

	print ("consumme:");
	print ( (gettime() -t) / 1000.0 );
}

testCalcNextPollardElement(4000);

